package demo.letcode.top100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
 *
 * 示例:
 *
 * 输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出:
 * [
 *   ["ate","eat","tea"],
 *   ["nat","tan"],
 *   ["bat"]
 * ]
 *
 * 分析
 * 字母异位词就是两个字符中的字母是一样的，只是顺序不同
 * 可以对字符进行排序，如果排序后字符相同，那么就是异位词
 * @author taqo
 * @date 2021/5/11
 */
public class _字母异位词分组 {
    public static void main(String[] args) {
        String strs[] = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> lists = groupAnagrams(strs);
        System.out.println(lists);
    }

    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String c = String.valueOf(chars);
            if (!map.containsKey(c)){
                map.put(c,new ArrayList<>());
            }
            map.get(c).add(str);
        }
        return new ArrayList<>(map.values());
    }
}
